# -*- coding: utf-8 -*-

'''
quick.py
Created on Junho de 2013
@authors: 
    Ricardo Barros, ESTIG,  EI pós-laboral n.º 5137
    Sergio Santos, ESTIG,  EI pós-laboral n.º 5626
'''

"""
O algoritmo "Quick Sort"

Tempo de execução:
    Pior cenário O(n^2);
    Melhor cenário O(n log(n));
    Caso médio O(n log(n)).

O algoritmo Quick-Sort aplica o paradigma de divisão e conquista.
  divisão è criada uma partição da tabela A[p, ... , r] em duas
     subtabelas, eventualmente vazias, A[p, ...., q-1] e A[q + 1, ... ,r]
  conquista ordenar as duas subtabelas A[p, ... , q -1] e
     A[q + 1, ..., r] atraés de chamadas recursivas à função Quick-Sort;
  combinação porque as subtabelas se encontram ordenadas não é
     necessário combinar os resultados encontrando-se ordenada a tabela A.

No pior cenário de partição a ordem de crescimento de é O(n2)^.
Isto corresponde ao caso em que a tabela de entrada já se encontra
ordenada.

No caso do melhor cenário de partição Partition produz dois
subproblemas com dimensão não superior a n/2, um de dimensão
n/2 e outro n/2-1, sendo O(n log(n)).

O tempo de execução para o caso médio é muito mais
próximo do melhor caso do que do pior caso.

Como utilizar:
 - EXEMPLO: Ordenação do array A:
 
    A = [2,8,7,1,3,5,6,4]
    print "antes: ", A
    quickSort(A, p=0, r=len(A)-1)
    print "depois: ", A

RESULTADO:
antes:  [2, 8, 7, 1, 3, 5, 6, 4]
depois:  [1, 2, 3, 4, 5, 6, 7, 8]
>>>

"""

import sys

sys.setrecursionlimit(100000)

def particion (A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i = i + 1
            A[i], A[j] = A[j], A[i]
    A[ i+1 ], A[ r ] = A[ r ], A[i+1]
    return i + 1
    
    
def quickSort(A, p, r):
    if p < r:
        q = particion(A, p, r)
        quickSort(A, p, q - 1)
        quickSort(A, q + 1,  r )
        
        
def main():
    A = [2,8,7,1,3,5,6,4]
    print "antes: ", A
    quickSort(A, p=0, r=len(A)-1)
    print "depois: ", A


if __name__ == '__main__':
    main()

        
        